Die Boost C++ Bibliotheken
Kapitel 13: Container
Inhaltsverzeichnis
Dieses Buch ist unter einer Creative Commons-Lizenz lizensiert.
13.1 Allgemeines
In diesem Kapitel lernen Sie verschiedene Boost C++ Bibliotheken kennen, die Container definieren und Ihnen daher zusätzlich zu den aus dem C++ Standard bekannten Containern zur Verfügung stehen. So erfahren Sie, wie Sie Container aus Boost.Unordered einsetzen, die im Technical Report 1 dem C++ Standard hinzugefügt wurden, wie Sie eigene Container mit Hilfe von Boost.Multiindex definieren und wann der Einsatz von Boost.Bimap sinnvoll ist - einer Bibliothek, die ihrerseits mit Hilfe von Boost.Multiindex entwickelt wurde. Die erste Bibliothek, die Sie kennenlernen werden, ist jedoch Boost.Array. Sie ermöglicht es, herkömmliche Arrays wie aus dem C++ Standard bekannte Container zu behandeln.
13.2 Boost.Array
Die Bibliothek Boost.Array definiert eine Template-Klasse boost::array in der Headerdatei boost/array.hpp. Mit dieser Klasse ist es möglich, ein Array zu erstellen, das die gleichen Eigenschaften besitzt wie ein herkömmliches in der Programmiersprache C++ definiertes Array. Weil boost::array darüberhinaus jedoch Anforderungen erfüllt, wie sie an im C++ Standard definierte Container gestellt werden, wird der Umgang mit einem Array ähnlich einfach wie mit jedem anderen Container. Grundsätzlich können Sie sich boost::array wie den aus dem C++ Standard bekannten Container std::vector vorstellen mit dem einzigen Unterschied, dass die Anzahl der Elemente in boost::array konstant ist.
#include <boost/array.hpp>
#include <iostream>
#include <string>
#include <algorithm>
int main()
{
typedef boost::array<std::string, 3> array;
array a;
a[0] = "Boris";
a.at(1) = "Anton";
*a.rbegin() = "Caesar";
std::sort(a.begin(), a.end());
for (array::const_iterator it = a.begin(); it != a.end(); ++it)
std::cout << *it << std::endl;
std::cout << a.size() << std::endl;
std::cout << a.max_size() << std::endl;
}
Wie Sie sehen ist der Einsatz von boost::array in der Tat sehr einfach. Das obige Beispiel bedarf keiner weiteren Erklärungen, da die aufgerufenen Methoden die gleiche Bedeutung haben wie bei dem aus dem C++ Standard bekannten Container std::vector.
Auf eine Besonderheit soll jedoch im folgenden Beispiel hingewiesen werden.
#include <boost/array.hpp>
#include <string>
int main()
{
typedef boost::array<std::string, 3> array;
array a = { "Boris", "Anton", "Caesar" };
}
Sie können ein Array vom Typ boost::array genauso initialisieren wie Sie es von herkömmlichen C++ Arrays gewohnt sind.
Da der hier vorgestellte Container im Technical Report 1 in den C++ Standard aufgenommen wurde, können Sie, wenn der Technical Report 1 von Ihrer Implementation des C++ Standards unterstützt wird, statt auf boost::array auf die Klasse std::array zugreifen, die in der Headerdatei array definiert ist.
13.3 Boost.Unordered
Boost.Unordered stellt den aus dem C++ Standard bekannten Containern std::set, std::multiset, std::map und std::multimap vier Klassen zur Seite: boost::unordered_set, boost::unordered_multiset, boost::unordered_map und boost::unordered_multimap. Diese Klassen bieten eine ähnliche Schnittstelle an wie die aus dem C++ Standard bekannten Container und unterscheiden sich auf den ersten Blick von diesen kaum. Sie können daher in vielen Fällen wahlweise einen Container aus dem C++ Standard nehmen oder einen aus Boost.Unordered - Ihr Programm wird sich nur minimal unterscheiden.
Der Unterschied zwischen den genannten Containern aus dem C++ Standard und Boost.Unordered ist, dass die Boost-Container Daten nicht sortieren und daher auch nicht voraussetzen, dass Werte eines Datentypen sortiert werden können. Boost.Unordered macht also immer dann Sinn, wenn eine Sortierung der im Container gespeicherten Daten unwichtig ist.
Um Daten dennoch schnell zu finden, werden Hash-Werte errechnet. Es handelt sich dabei um Nummern, die Daten in einem Container eindeutig identifizieren und die beispielsweise schneller verglichen werden können als andere Datentypen wie Strings. Weil Hash-Werte errechnet werden, müssen Datentypen, die in Containern von Boost.Unordered gespeichert werden sollen, die Generierung dieser Identifikationsnummern unterstützen. Während also zum Beispiel std::set voraussetzt, dass Daten sortiert werden können, verlangt boost::unordered_set, dass Hash-Werte errechnet werden können. Auch wenn dies eine Anforderung ist, die von Boost.Unordered gestellt wird: Grundsätzlich ist Boost.Unordered den Containern aus dem C++ Standard vorzuziehen. Nur dann, wenn Sie eine Sortierung wünschen, sollten Sie die Container aus dem C++ Standard verwenden.
Im Folgenden sehen Sie beispielhaft, wie boost::unordered_set eingesetzt wird.
#include <boost/unordered_set.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::unordered_set<std::string> unordered_set;
unordered_set set;
set.insert("Boris");
set.insert("Anton");
set.insert("Caesar");
for (unordered_set::iterator it = set.begin(); it != set.end(); ++it)
std::cout << *it << std::endl;
std::cout << set.size() << std::endl;
std::cout << set.max_size() << std::endl;
std::cout << (set.find("David") != set.end()) << std::endl;
std::cout << set.count("Boris") << std::endl;
}
Wie Sie sehen bietet boost::unordered_set ähnliche Methoden wie std::set an. So könnte im obigen Programm auch std::set verwendet werden, ohne dass viele Änderungen im Quellcode notwendig wären.
Im folgenden Beispiel wird boost::unordered_map verwendet, um zusätzlich zum Namen das Alter der jeweiligen Person zu speichern.
#include <boost/unordered_map.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::unordered_map<std::string, int> unordered_map;
unordered_map map;
map.insert(unordered_map::value_type("Boris", 31));
map.insert(unordered_map::value_type("Anton", 35));
map.insert(unordered_map::value_type("Caesar", 25));
for (unordered_map::iterator it = map.begin(); it != map.end(); ++it)
std::cout << it->first << ", " << it->second << std::endl;
std::cout << map.size() << std::endl;
std::cout << map.max_size() << std::endl;
std::cout << (map.find("David") != map.end()) << std::endl;
std::cout << map.count("Boris") << std::endl;
}
Auch hier werden Sie keine großen Unterschiede zwischen boost::unordered_map und std::map feststellen. Das obige Programm könnte auch problemlos mit std::map implementiert werden.
Sie haben bereits erfahren, dass Boost.Unordered erwartet, dass für Daten, die in den Containern gespeichert werden sollen, Hash-Werte errechnet werden können. Verschiedene Datentypen wie beispielsweise std::string werden von den Containern aus Boost.Unordered von Haus aus unterstützt. Für benutzerdefinierte Datentypen muss jedoch eine Hash-Funktion definiert werden, die von Boost.Unordered verwendet werden kann.
#include <boost/unordered_set.hpp>
#include <string>
struct person
{
std::string name;
int age;
person(const std::string &n, int a)
: name(n), age(a)
{
}
bool operator==(const person &p) const
{
return name == p.name && age == p.age;
}
};
std::size_t hash_value(person const &p)
{
std::size_t seed = 0;
boost::hash_combine(seed, p.name);
boost::hash_combine(seed, p.age);
return seed;
}
int main()
{
typedef boost::unordered_set<person> unordered_set;
unordered_set set;
set.insert(person("Boris", 31));
set.insert(person("Anton", 35));
set.insert(person("Caesar", 25));
}
Im obigen Programm sollen Daten vom Typ person in einem Container vom Typ boost::unordered_set gespeichert werden. Weil die Hash-Funktion von boost::unordered_set die Klasse person nicht kennt, können keine Hash-Werte für Daten dieses Typs errechnet werden. Deswegen muss eine Hash-Funktion definiert werden - andernfalls würde der Code nicht kompilieren.
Der Name der Hash-Funktion, die definiert werden muss, lautet hash_value(). Sie muss als einzigen Parameter ein Objekt des Datentyps erwarten, von dem ein Hash-Wert gebildet werden soll. Weil ein Hash-Wert einfach nur eine Nummer ist, muss der Datentyp des Rückgabewertes von hash_value() std::size_t sein.
Die Funktion hash_value() wird automatisch aufgerufen, wenn der Hash-Wert für ein Objekt errechnet werden soll. Diese Funktion ist für verschiedene Datentypen in den Boost C++ Bibliotheken bereits definiert - unter anderem für std::string. Für benutzerdefinierte Datentypen wie person muss sie vom Entwickler definiert werden.
Die Definition von hash_value() ist dabei üblicherweise sehr einfach: Der Hash-Wert wird gebildet, indem nacheinander auf die verschiedenen Bestandteile des Objekts zugegriffen wird. Dies geschieht über die Funktion boost::hash_combine(), die aus der Bibliothek Boost.Hash stammt und in der Headerdatei boost/functional/hash.hpp definiert ist. Sie müssen diese Headerdatei jedoch nicht einbinden, wenn Sie Boost.Unordered verwenden, da sämtliche Container in dieser Bibliothek zum Errechnen von Hash-Werten auf Boost.Hash zugreifen.
Neben der Definition der Funktion hash_value() muss es außerdem möglich sein, zwei Objekte mit == zu vergleichen. Deswegen ist für die Klasse person im obigen Beispiel die Methode operator==() definiert worden.
13.4 Boost.Multiindex
Die Bibliothek Boost.Multiindex ist ein Stück komplizierter als die bisher in diesem Kapitel vorgestellten Boost C++ Bibliotheken. Während Boost.Array und Boost.Unordered fertige Container anbieten, die direkt verwendet werden können, ermöglicht Boost.Multiindex, neue Container zu definieren. Diese Container bieten dann nicht wie die aus dem C++ Standard bekannten Container eine einzige Sichtweise auf Daten an, sondern können beliebig viele Schnittstellen unterstützen. So können Sie einen Container erstellen, der ähnlich wie std::map Werte Schlüsseln zuordnet, gleichzeitig aber auch umgekehrt die Werte als Schlüssel verwenden kann - etwas, was Sie ohne Boost.Multiindex mit zwei Containern vom Typ std::map entwickeln müssten. Dabei müssten Sie außerdem darauf achten, dass beide Container laufend synchronisiert werden, damit sie zu jedem Zeitpunkt die gleichen Daten speichern.
Im folgenden Beispiel wird mit Hilfe von Boost.Multiindex ein neuer Container definiert, in dem der Name und das Alter von Personen gespeichert werden kann. Im Gegensatz zu std::map kann jedoch sowohl nach Name als auch nach Alter gesucht werden.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
struct person
{
std::string name;
int age;
person(const std::string &n, int a)
: name(n), age(a)
{
}
};
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, std::string, &person::name
>
>,
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, int, &person::age
>
>
>
> person_multi;
int main()
{
person_multi persons;
persons.insert(person("Boris", 31));
persons.insert(person("Anton", 35));
persons.insert(person("Caesar", 25));
std::cout << persons.count("Boris") << std::endl;
const person_multi::nth_index<1>::type &age_index = persons.get<1>();
std::cout << age_index.count(25) << std::endl;
}
Wie bereits erwähnt stellt Boost.Multiindex keinen Container zur Verfügung, sondern Klassen, um einen neuen Container zu definieren. Der erste Schritt ist daher typischerweise, über typedef auf verschiedene Klassen in Boost.Multiindex zuzugreifen und genau den Container zu konstruieren, den man verwenden möchte.
Eine Klasse, die bei jeder Container-Definition benötigt wird, ist boost::multi_index::multi_index_container. Sie ist in der Headerdatei boost/multi_index_container.hpp definiert. Da es sich bei boost::multi_index::multi_index_container um ein Template handelt, müssen mindestens zwei Parameter angegeben werden. Der erste Parameter ist der Datentyp, der im Container gespeichert werden soll - im obigen Programm eine benutzerdefinierte Klasse person. Der zweite Parameter wird verwendet, um die verschiedenen Indizes festzulegen, die vom Container zur Verfügung gestellt werden sollen.
Der entscheidende Vorteil, den Container auf Basis von Boost.Multiindex bieten, ist, dass auf Daten über unterschiedliche Schnittstellen zugegriffen werden kann. Bei einer Container-Definition kann nun angegeben werden, wie viele und welche Schnittstellen ein Container anbieten soll. Da für das obige Programm ein Container benötigt wird, mit dem sowohl über den Namen als auch über das Alter nach Personen gesucht werden kann, werden in diesem Fall zwei Schnittstellen definiert. Boost.Multiindex nennt diese Schnittstellen Indizes - daher auch der Name dieser Bibliothek.
Die Definition von Schnittstellen erfolgt über die Klasse boost::multi_index::indexed_by. Auch bei dieser Klasse handelt es sich um ein Template, dem mehrere Parameter übergeben werden können, wobei jeder Parameter eine Schnittstelle definiert. Im obigen Programm werden zwei Schnittstellen vom Typ boost::multi_index::hashed_non_unique definiert, deren Definition sich in der Headerdatei boost/multi_index/hashed_index.hpp befindet. Diese Schnittstelle wird verwendet, wenn sich ein Container ähnlich wie die in Boost.Unordered definierten Container verhalten soll und Daten intern mit Hilfe eines Hash-Werts gespeichert werden sollen.
Auch die Klasse boost::multi_index::hashed_non_unique ist ein Template. Sie erwartet als einzigen Parameter eine Klasse, die sie zur Berechnung von Hash-Werten verwenden kann. Da die beiden Schnittstellen des Containers den Zugriff auf Personen über Namen und Alter ermöglichen sollen, soll die eine Schnittstellen Hash-Werte für Namen und die andere Schnittstelle für Alter errechnen.
Boost.Multiindex bietet für den Zugriff auf eine Eigenschaft eine Hilfsklasse boost::multi_index::member an. Sie ist in der Headerdatei boost/multi_index/member.hpp definiert. Da es sich auch bei dieser Klasse um ein Template handelt, müssen so wie im obigen Programm geschehen mehrere Parameter angegeben werden, damit boost::multi_index::member weiß, auf welche Eigenschaft von person zugegriffen werden soll und welchen Datentyp die Eigenschaft hat.
Auch wenn die Klassendefinition von person_multi auf den ersten Blick sehr kompliziert aussieht: Diese Klasse funktioniert ähnlich wie boost::unordered_map aus der Bibliothek Boost.Unordered mit dem entscheidenden Unterschied, dass sowohl der Name als auch das Alter einer Person als Schlüssel zum Suchen von Daten im Container verwendet werden kann.
Wenn Sie auf einen Multiindex-Container zugreifen, müssen Sie grundsätzlich angeben, welche Schnittstelle Sie für den Zugriff verwenden wollen. Die einzige Ausnahme ist die als erste definierte Schnittstelle. Wenn wie im obigen Beispiel per insert() oder count() direkt auf das Objekt persons zugegriffen wird, wird implizit die erste Schnittstelle verwendet - in diesem Fall also der Hash-Container für die Eigenschaft name. Möchten Sie über eine andere als die erste Schnittstelle auf einen Multiindex-Container zugreifen, müssen Sie sie explizit auswählen.
Schnittstellen sind durchnummiert, wobei die erste Schnittstelle den Index 0 besitzt. Wenn Sie wie im obigen Beispiel auf die zweite Schnittstelle zugreifen möchten, können Sie dies über get() machen. Sie müssen dieser Methode, die ein Template ist, den Index der gewünschten Schnittstelle als Template-Parameter übergeben.
Der Rückgabewert von get() sieht ein wenig kompliziert aus: Sie greifen auf eine Klasse im Multiindex-Container zu, die nth_index heißt. Weil es sich hier wiederum um ein Template handelt, müssen Sie den Index der Schnittstelle, die Sie verwenden wollen, als Template-Parameter angeben. Dieser Index muss der gleiche sein wie der, den Sie als Template-Parameter an get() übergeben haben. Wenn Sie dann noch über :: auf die Typdefinition type der Klasse nth_index zugreifen, haben Sie es geschafft. Dieses type repräsentiert den Typ der entsprechenden Schnittstelle.
Sie müssen zwar nicht wissen, wie die Typdefinition einer Schnittstelle exakt aussieht, weil sie wie gesehen über nth_index und type automatisch abgeleitet werden kann. Sie sollten aber dennoch wissen, auf welche Art von Schnittstelle Sie nun eigentlich zugreifen. Das sollte sich aber von selbst verstehen: Da Sie den Index der Schnittstelle an get() und nth_index übergeben und in der Container-Definition nachsehen können, in welcher Reihenfolge Schnittstellen definiert wurden, wissen Sie, welche Art von Schnittstelle Ihnen dann zur Verfügung steht. So gilt für obiges Beispiel: age_index ist ebenfalls eine Hash-Schnittstelle, nur dass in diesem Fall auf Personen nicht über den Namen, sondern über das Alter zugegriffen wird.
Wenn in einem Multiindex-Container wie im vorherigen Beispiel Daten wie Name und Alter je nach Schnittstelle Schlüssel sein können, dürfen sie nicht mehr beliebig geändert werden können. Wenn zum Beispiel nach einer Person mit einem bestimmten Namen gesucht wird und dann das Alter der Person geändert werden würde, wüsste die andere Schnittstelle, die das Alter der Personen als Schlüssel verwendet, nicht, dass einer der Schlüssel geändert wurde und zum Beispiel ein neuer Hash-Wert errechnet werden muss.
So wie es nicht möglich ist, den Schlüssel in einem Container vom Typ std::map zu ändern, können Daten in einem Multiindex-Container ebenfalls nicht geändert werden. Grundsätzlich sind also alle Daten, die in einem Multiindex-Container gespeichert wurden, konstant. Damit nun aber nicht Daten gelöscht und dann in geänderter Form wieder gespeichert werden müssen, bietet Boost.Multiindex ein paar nützliche Methoden an, mit denen Daten direkt geändert werden können. Da diese Methoden für den Multiindex-Container aufgerufen werden und keine Daten im Multiindex-Container über einen direkten Zugriff auf das entsprechende Objekt geändert werden, ist diese Art der Datenaktualisierung sicher. So werden in diesem Fall sämtliche Schnittstellen benachrichtigt und können zum Beispiel Hash-Werte aktualisieren.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
struct person
{
std::string name;
int age;
person(const std::string &n, int a)
: name(n), age(a)
{
}
};
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, std::string, &person::name
>
>,
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, int, &person::age
>
>
>
> person_multi;
void set_age(person &p)
{
p.age = 32;
}
int main()
{
person_multi persons;
persons.insert(person("Boris", 31));
persons.insert(person("Anton", 35));
persons.insert(person("Caesar", 25));
person_multi::iterator it = persons.find("Boris");
persons.modify(it, set_age);
const person_multi::nth_index<1>::type &age_index = persons.get<1>();
std::cout << age_index.count(32) << std::endl;
}
Die Methode modify() wird von allen Schnittstellen unterstützt, die Boost.Multiindex anbietet. Sie kann daher immer direkt für den Multiindex-Container aufgerufen werden. Ihr muss als erster Parameter ein Iterator auf ein Objekt im Container übergeben werden, das geändert werden soll. Der zweite Parameter ist eine Funktion oder ein Funktionsobjekt, dem beim Aufruf als einziger Parameter ein Objekt von dem Datentyp übergeben wird, der im Multiindex-Container gespeichert ist - im obigen Beispiel also person. In dieser Funktion - hier set_age() genannt - kann also ein Objekt im Container geändert werden.
Bisher haben Sie lediglich eine einzige Schnittstelle kennengelernt: Mit boost::multi_index::hashed_non_unique werden für Daten Hash-Werte errechnet, wobei diese nicht einmalig sein müssen. Wenn Sie möchten, dass keine Daten zweimal im Container gespeichert werden dürfen, können Sie boost::multi_index::hashed_unique verwenden. Beachten Sie hierbei, dass Container Daten nicht speichern können, wenn nicht alle Anforderungen von allen Schnittstellen des Containers erfüllt sind. Wenn also eine Schnittstelle keine Kopien von Daten akzeptiert, dann hilft es auch nicht, wenn andere Schnittstellen diese akzeptieren. Sehen Sie sich dazu untenstehendes Beispiel an.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
struct person
{
std::string name;
int age;
person(const std::string &n, int a)
: name(n), age(a)
{
}
};
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, std::string, &person::name
>
>,
boost::multi_index::hashed_unique<
boost::multi_index::member<
person, int, &person::age
>
>
>
> person_multi;
int main()
{
person_multi persons;
persons.insert(person("Boris", 31));
persons.insert(person("Anton", 31));
persons.insert(person("Caesar", 25));
const person_multi::nth_index<1>::type &age_index = persons.get<1>();
std::cout << age_index.count(31) << std::endl;
}
Der Multiindex-Container verwendet nun als zweite Schnittstelle die Klasse boost::multi_index::hashed_unique. Das bedeutet, dass keine zwei Personen das gleiche Alter haben dürfen. Denn dann würde für beide Personen logischerweise der gleiche Hash-Wert errechnet werden - und der muss, was die zweite Schnittstelle betrifft, einmalig sein.
Weil im Programm nun versucht wird, eine Person namens Anton zu speichern, die genauso alt ist wie die bereits im Container gespeicherte Person Boris, wird das Objekt nicht akzeptiert. Denn die Anforderungen der zweiten Schnittstelle, dass Hash-Werte für Alter eindeutig sein müssen, könnten dann nicht mehr erfüllt werden. Deswegen gibt das Programm den Wert 1 auf den Bildschirm aus, wenn es nach Personen mit dem Alter 31 sucht - es wurde lediglich die Person namens Boris im Container gespeichert.
Im folgenden Beispielprogramm sollen Ihnen die anderen drei Schnittstellen, die Boost.Multiindex anbietet, vorgestellt werden: boost::multi_index::sequenced, boost::multi_index::ordered_non_unique und boost::multi_index::random_access.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
struct person
{
std::string name;
int age;
person(const std::string &n, int a)
: name(n), age(a)
{
}
};
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
boost::multi_index::sequenced<>,
boost::multi_index::ordered_non_unique<
boost::multi_index::member<
person, int, &person::age
>
>,
boost::multi_index::random_access<>
>
> person_multi;
int main()
{
person_multi persons;
persons.push_back(person("Boris", 31));
persons.push_back(person("Anton", 31));
persons.push_back(person("Caesar", 25));
const person_multi::nth_index<1>::type &ordered_index = persons.get<1>();
person_multi::nth_index<1>::type::iterator lower = ordered_index.lower_bound(30);
person_multi::nth_index<1>::type::iterator upper = ordered_index.upper_bound(40);
for (; lower != upper; ++lower)
std::cout << lower->name << std::endl;
const person_multi::nth_index<2>::type &random_access_index = persons.get<2>();
std::cout << random_access_index[2].name << std::endl;
}
Über die Schnittstelle boost::multi_index::sequenced können Sie einen Multiindex-Container wie eine Liste behandeln - also ähnlich wie std::list. Wie Sie anhand des obigen Programms sehen, wird diese Schnittstelle bei der Definition des Containers recht einfach verwendet: Es ist keine Angabe von Template-Parametern notwendig. Die Objekte vom Typ person, die diesem Container hinzugefügt werden, werden also aus Sicht von boost::multi_index::sequenced genau in der angegebenen Reihenfolge gespeichert.
Wenn Sie die Schnittstelle boost::multi_index::ordered_non_unique verwenden, werden Objekte automatisch sortiert. Für diese Schnittstelle müssen Sie bei der Definition des Containers angeben, wie die Sortierung genau erfolgen soll. So wird im obigen Programm angegeben, dass Objekte vom Typ person über das Alter sortiert werden sollen. Dazu wird auf die bereits bekannte Hilfsklasse boost::multi_index::member zugegriffen.
Da boost::multi_index::ordered_non_unique Daten sortiert, bietet die Schnittstelle spezielle Methoden an, um bestimmte Positionen innerhalb der sortierten Daten zu finden. So werden im obigen Beispiel über lower_bound() und upper_bound() alle Personen gesucht, die mindestens 30 und höchstens 40 Jahre alt sind. Diese Methoden werden von keiner anderen Schnittstelle angeboten, da sie eine Sortierung voraussetzen.
Die dritte Schnittstelle, die im obigen Programm zur Containerdefinition eingesetzt wird, ist boost::multi_index::random_access. Über diese Schnittstelle kann ein Multiindex-Container wie ein Vektor vom Typ std::vector behandelt werden. Die beiden prominentesten Methoden sind operator[]() und at().
Beachten Sie, dass boost::multi_index::random_access die Schnittstelle boost::multi_index::sequenced vollständig einschließt. Wenn Sie zur Containerdefinition boost::multi_index::random_access verwenden, macht es demnach nicht wirklich Sinn, zusätzlich boost::multi_index::sequenced einzusetzen, da sämtliche Methoden dieser Schnittstelle auch über boost::multi_index::random_access zur Verfügung stehen.
Während Sie nun die vier Schnittstellen, die Boost.Multiindex anbietet, kennengelernt haben, soll im Folgenden ein Blick auf die sogenannten Schlüsselentnehmer geworfen werden. Einen Schlüsselentnehmer haben Sie bereits in den Beispielen gesehen: boost::multi_index::member aus der Headerdatei boost/multi_index/member.hpp. Diese Hilfsklasse wird Schlüsselentnehmer genannt, da mit ihr genau angegeben werden kann, welche Eigenschaft einer Klasse als Schlüssel in einer Schnittstelle verwendet werden soll.
Im folgenden Beispiel lernen Sie zwei weitere Schlüsselentnehmer kennen.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <iostream>
#include <string>
class person
{
public:
person(const std::string &n, int a)
: name(n), age(a)
{
}
bool operator<(const person &p) const
{
return age < p.age;
}
std::string get_name() const
{
return name;
}
private:
std::string name;
int age;
};
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
boost::multi_index::ordered_unique<
boost::multi_index::identity<person>
>,
boost::multi_index::hashed_unique<
boost::multi_index::const_mem_fun<
person, std::string, &person::get_name
>
>
>
> person_multi;
int main()
{
person_multi persons;
persons.insert(person("Boris", 31));
persons.insert(person("Anton", 31));
persons.insert(person("Caesar", 25));
std::cout << persons.begin()->get_name() << std::endl;
const person_multi::nth_index<1>::type &hashed_index = persons.get<1>();
std::cout << hashed_index.count("Boris") << std::endl;
}
Der Schlüsselentnehmer boost::multi_index::identity, definiert in der Headerdatei boost/multi_index/identity.hpp, wird verwendet, um den Datentypen, der im Multiindex-Container gespeichert wird, selbst als Schlüssel zu verwenden. Für das obige Beispiel bedeutet dies, dass die Klasse person sortiert werden können muss, weil der Datentyp selbst als Schlüssel für die Schnittstelle boost::multi_index::ordered_unique angegeben ist. Das ist der Grund, warum die Methode operator<() für die Klasse person überladen wurde.
In der Headerdatei boost/multi_index/mem_fun.hpp sind die beiden Schlüsselentnehmer boost::multi_index::const_mem_fun und boost::multi_index::mem_fun definiert, mit denen der Rückgabewert einer Methode als Schlüssel verwendet werden kann. Im obigen Programm ist dies der Rückgabewert von get_name(). boost::multi_index::const_mem_fun wird hierbei für konstante Methoden verwendet, boost::multi_index::mem_fun für nicht-konstante Methoden.
Boost.Multiindex bietet zwei weitere Schlüsselentnehmer namens boost::multi_index::global_fun und boost::multi_index::composite_key an. Während der erstgenannte Schlüsselentnehmer für freistehende Funktionen und statische Methoden verwendet werden kann, ermöglicht boost::multi_index::composite_key, einen Schlüsselentnehmer bestehend aus mehreren anderen Schlüsselentnehmern zu konstruieren.
13.5 Boost.Bimap
Die Bibliothek Boost.Bimap basiert auf Boost.Multiindex und bietet einen Container an, den Sie sofort nutzen können, ohne dass Sie ihn erst selbst definieren müssen. Es handelt sich hierbei um einen Container ähnlich std::map, wobei nicht einseitig nach Schlüsseln, sondern auch nach Werten gesucht werden kann. Schauen Sie sich dazu folgendes Beispiel an.
#include <boost/bimap.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::bimap<std::string, int> bimap;
bimap persons;
persons.insert(bimap::value_type("Boris", 31));
persons.insert(bimap::value_type("Anton", 31));
persons.insert(bimap::value_type("Caesar", 25));
std::cout << persons.left.count("Boris") << std::endl;
std::cout << persons.right.count(31) << std::endl;
}
Der Container boost::bimap, definiert in der Headerdatei boost/bimap.hpp, bietet zwei Eigenschaften left und right an, mit denen quasi auf die beiden Container vom Typ std::map zugegriffen werden kann, die boost::bimap vereint. Während über left auf den Container zugegriffen wird, der im obigen Programm Werte vom Typ std::string als Schlüssel verwendet, können über right int-Werte als Schlüssel verwendet werden.
Neben dem Zugriff auf Datensätze sowohl über einen linken als auch rechten Container gestattet boost::bimap auch, Datensätze als Relationen zu betrachten. Sehen Sie sich dazu folgendes Beispiel an.
#include <boost/bimap.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::bimap<std::string, int> bimap;
bimap persons;
persons.insert(bimap::value_type("Boris", 31));
persons.insert(bimap::value_type("Anton", 31));
persons.insert(bimap::value_type("Caesar", 25));
for (bimap::iterator it = persons.begin(); it != persons.end(); ++it)
std::cout << it->left << " is " << it->right << " years old." << std::endl;
}
Es ist also nicht notwendig, jeweils über left oder right auf Datensätze im Container zuzugreifen. Sie können auch direkt über Datensätze iterieren und dann über den Iterator auf die linke oder rechte Seite des jeweiligen Datensatzes zugreifen.
Während es für std::map einen Container namens std::multimap gibt, der mehrere Datensätze mit gleichem Schlüssel speichern kann, gibt es keinen entsprechenden Container neben boost::bimap. Das heißt aber nicht, dass es nicht möglich wäre, Datensätze mit gleichem Schlüssel in einem Container vom Typ boost::bimap zu speichern. Denn die beiden Template-Parameter, die für boost::bimap angegeben werden müssen, geben genaugenommen nicht Datentypen an, die gespeichert werden sollen, sondern Containertypen, die für left und right verwendet werden sollen. Wird wie in den obigen Beispielen kein Containertyp angegeben, sondern einfach nur std::string und int, wird automatisch der Containertyp boost::bimaps::set_of verwendet. Und dieser erlaubt ähnlich wie std::map nur Datensätze mit eindeutigem Schlüssel.
Das erste Beispiel zu boost::bimap lässt sich demnach auch wie folgt schreiben.
#include <boost/bimap.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::bimap<boost::bimaps::set_of<std::string>, boost::bimaps::set_of<int>> bimap;
bimap persons;
persons.insert(bimap::value_type("Boris", 31));
persons.insert(bimap::value_type("Anton", 31));
persons.insert(bimap::value_type("Caesar", 25));
std::cout << persons.left.count("Boris") << std::endl;
std::cout << persons.right.count(31) << std::endl;
}
Neben boost::bimaps::set_of, der Datensätze wie std::map sortiert und darauf achtet, dass Schlüssel eindeutig sind, stehen mehrere andere Containertypen zur Verfügung, mit denen boost::bimap angepasst werden kann.
#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::bimap<boost::bimaps::set_of<std::string>, boost::bimaps::multiset_of<int>> bimap;
bimap persons;
persons.insert(bimap::value_type("Boris", 31));
persons.insert(bimap::value_type("Anton", 31));
persons.insert(bimap::value_type("Caesar", 25));
std::cout << persons.left.count("Boris") << std::endl;
std::cout << persons.right.count(31) << std::endl;
}
Im obigen Programm wird der Containertyp boost::bimaps::multiset_of verwendet, der in der Headerdatei boost/bimap/multiset_of.hpp definiert ist. Er funktioniert ähnlich wie boost::bimaps::set_of, nur dass Schlüssel nicht mehr eindeutig sein müssen. Somit gibt obiges Programm nun für die Anzahl der 31-jährigen Personen 2 aus.
Beachten Sie, dass Sie für andere Containertypen als boost::bimaps::set_of die entsprechenden Headerdateien einbinden müssen. Weil boost::bimaps::set_of standardmäßig in Containern vom Typ boost::bimap verwendet wird, müssen Sie die entsprechende Headerdatei boost/bimap/set_of.hpp nicht einbinden.
Neben den bisher kennengelernten Containertypen bietet Boost.Bimap die Klassen boost::bimaps::unordered_set_of, boost::bimaps::unordered_multiset_of, boost::bimaps::list_of, boost::bimaps::vector_of und boost::bimaps::unconstrainted_set_of an. Bis auf die Klasse boost::bimaps::unconstrainted_set_of, die weiterer Erläuterungen bedarf, funktionieren alle anderen genannten Containertypen wie die aus dem C++ Standard und aus Boost.Unordered bekannten Klassen.
#include <boost/bimap.hpp>
#include <boost/bimap/unconstrained_set_of.hpp>
#include <boost/bimap/support/lambda.hpp>
#include <iostream>
#include <string>
int main()
{
typedef boost::bimap<std::string, boost::bimaps::unconstrained_set_of<int>> bimap;
bimap persons;
persons.insert(bimap::value_type("Boris", 31));
persons.insert(bimap::value_type("Anton", 31));
persons.insert(bimap::value_type("Caesar", 25));
bimap::left_map::iterator it = persons.left.find("Boris");
persons.left.modify_key(it, boost::bimaps::_key = "Doris");
std::cout << it->first << std::endl;
}
Mit boost::bimaps::unconstrainted_set_of kann wie im obigen Programm geschehen eine Seite von boost::bimap ausgeschaltet werden. Es ist dann nicht mehr möglich, über right auf die rechte Seite des Containers zuzugreifen und Personen nach ihrem Alter zu durchsuchen. In diesem Fall verhält sich der Container vom Typ boost::bimap also genauso wie der aus dem C++ Standard bekannte Container std::map.
Warum es trotzdem sinnvoll sein kann, statt std::map boost::bimap einzusetzen, sehen Sie auch anhand des obigen Beispiels. Da Boost.Bimap auf Boost.Multiindex basiert, stehen aus Boost.Multiindex bekannte Methoden zur Verfügung. So wird im obigen Programm über modify_key() ein Schlüssel geändert - etwas, was mit std::map nicht möglich ist.
Beachten Sie außerdem, wie der Schlüssel im Detail geändert wird: Über boost::bimaps::_key, das in der Headerdatei boost/bimap/support/lambda.hpp definiert ist, wird auf den aktuellen Schlüssel zugegriffen und ihm ein neuer Wert zugewiesen. Es handelt sich hierbei also um eine Lambda-Funktion, wie Sie sie im Kapitel 3, Funktionsobjekte kennengelernt haben.
Neben boost::bimaps::_key ist in der Headerdatei boost/bimap/support/lambda.hpp auch boost::bimaps::_data definiert. Beim Aufruf der Methode modify_data() können Sie entsprechend einen Wert in einem Container vom Typ boost::bimap ändern.
13.6 Aufgaben
Sie können die Lösungen zu allen Aufgaben in diesem Buch als ZIP-Datei erwerben.
Entwickeln Sie ein Programm, das Mitarbeiter einer Firma Abteilungen zuordnet. Speichern Sie ein paar Beispieldatensätze ab und durchsuchen Sie diese, um herauszufinden, in welcher Abteilung ein bestimmter Mitarbeiter beschäftigt ist und wie viele Mitarbeiter in einer bestimmten Abteilung arbeiten.
Erweitern Sie Ihr Programm aus Aufgabe 1, indem Sie zusätzlich Mitarbeitern Nummern zuordnen. Diese müssen eindeutig sein, damit Mitarbeiter mit gleichem Namen eindeutig identifiziert werden können. Durchsuchen Sie Ihre Beispieldatensätze, um die Daten eines Mitarbeiters mit einer bestimmten Nummer auszugeben.